package 算法shiyan;/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/5/14 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

import java.util.Scanner;

/**
 * @ProjectName: projectweb
 * @ClassName: 贪心算法TSP
 * @Description: 请描述该类的功能
 * @Author: 1913040634刘世锦
 * @Date: 2021/5/14 19:33 .
 * @version v1.0
 */
public class 贪心算法TSP {
    public static void main(String[] args) {
        int n = 0;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int [][] sd = new int[n][n]; //城市之间的距离
        int [] sq = new int [n];//存储距离
        int max = 100;
        for (int i = 0; i < n; i++) {
            sq[i] = max;
        }
        //构造城市距离的矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sd[i][j] = sc.nextInt();
            }
        }

//        int [][] arc= {{max,3,3,2,6},{3,max,7,3,2},{3,7,max,2,5}, {2,3,2,max,3},{6,2,5,3,max}};
        int minDist = TSP(sd, 0);
        System.out.println(minDist);
    }
   public static int TSP (int sd[][] , int w ){  //从w出发
        int edgecount = 0, TSPlength = 0;
        int min,u;
        int v  = 0;
        int [ ]flaga = new int[5];//顶点未加入回路
    int []flag= {0, 0, 0, 0, 0};
       u = w;
        flag[w] = 1;
        while ( edgecount <5-1){ //想你换直到边数等于n-1
            min = 100;
            for(int j= 0;j<5;j++){
                if(flag[j]==0 && (sd[u][j]!=0)  &&(sd[u][j]<min)){//可达下一个节点且代价最小

                    v = j;
                    min = sd[u][j];
                }

            }
            TSPlength  += sd[u][v];
            flag[v] = 1;//顶点加入回路
            edgecount++;

            System.out.println(u+" --> "+v);
            u=v;
        }

       System.out.println(v+" --> "+w);
        return(TSPlength+sd[u][w]);

    }
}
